package leetcode.divideandconquer;

import java.util.ArrayList;
import java.util.List;

public class DiﬀerentWaysToAddParentheses241 {
    class Solution1 {
        public List<Integer> diffWaysToCompute(String expression) {
            List<Integer> ans = new ArrayList<>();
            for (int i = 0; i < expression.length(); i++) {
                char c = expression.charAt(i);
                if (c == '-' || c == '+' || c == '*') {
                    List<Integer> left = diffWaysToCompute(expression.substring(0, i));
                    List<Integer> right = diffWaysToCompute(expression.substring(i + 1));
                    for (int l : left) {
                        for (int r : right) {
                            switch (c) {
                                case '+':
                                    ans.add(l + r);
                                    break;
                                case '-':
                                    ans.add(l - r);
                                    break;
                                case '*':
                                    ans.add(l * r);
                                    break;
                            }
                        }
                    }
                }
            }
            if (ans.isEmpty()) {
                ans.add(Integer.valueOf(expression));
            }
            return ans;
        }
    }



}

